package com.wangjie.doublepointer;

import java.util.PriorityQueue;

/**
 * @author jieshao
 * @date 2022/4/12 15:12
 *
 * 快慢指针技巧
 */
public class FastSlowPointer {
    /**
     * 876. 链表的中间结点
     *
     * 解题思路：用两个指针 slow 和 fast 分别指向链表头结点 head，慢指针一次前进一步，快指针一次前进两步，当快指针到达链表末尾时，慢指针就处于链表的中间位置
     *
     * @param head 链表的头节点
     * @return
     */
    public ListNode middleNode(ListNode head) {
        // 快慢指针初始化指向 head
        ListNode slow = head, fast = head;
        // 快指针走到末尾时停止
        while (fast != null && fast.next != null) {
            // 慢指针走一步，快指针走两步
            slow = slow.next;
            fast = fast.next.next;
        }
        // 慢指针指向中点
        return slow;
    }

    /**
     * 141. 环形链表
     *
     * 解题思路：用两个指针，一个跑得快，一个跑得慢。如果不含有环，跑得快的那个指针最终会遇到null，说明链表不含环；如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环。
     *
     * @param head 链表的头节点
     * @return
     */
    public boolean hasCycle(ListNode head) {
        // 快慢指针初始化指向 head
        ListNode slow = head, fast = head;
        // 快指针走到末尾时停止
        while (fast != null && fast.next != null) {
            // 慢指针走一步，快指针走两步
            slow = slow.next;
            fast = fast.next.next;
            // 快慢指针相遇，说明含有环
            if (slow == fast) {
                return true;
            }
        }
        // 不含环
        return false;
    }

    /**
     * 进阶版：如果链表中含有环，如何计算这个环的起点？
     *
     * 解题思路：当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置
     *
     * @param head 链表的头节点
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                break;
            }
        }

        // fast 为空说明不含环
        if (fast == null || fast.next == null) {
            return null;
        }

        // 慢指针重新指向头节点
        slow = head;
        // 快慢指针同步前进，相交点即是环起点
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    /**
     * 寻找单链表的倒数第 k 个节点
     *
     * @param head 链表的头节点
     * @param k    倒数第 k 个节点
     * @return
     */
    ListNode findFromEnd(ListNode head, int k) {
        // 快慢指针初始化指向 head
        ListNode slow = head, fast = head;
        // 快指针先走 k 步
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        // 快指针走到末尾时停止
        while (fast != null) {
            // 快指针和慢指针同时走 (n - k) 步
            slow = slow.next;
            fast = fast.next;
        }
        // 此时，慢指针指向第 (n - k) 个节点
        return slow;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     *
     * @param head 链表的头节点
     * @param n    倒数第 n 个节点
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 虚拟头节点
        ListNode dummy = new ListNode(0, head);
        ListNode fast = head;
        ListNode slow = dummy;
        // 快指针先走 n 步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 删除链表的倒数第 n 个结点
        slow.next = slow.next.next;
        return dummy.next;
    }

    /**
     * 21. 合并两个有序链表
     *
     * 这个算法的逻辑类似于拉拉链，list1, list2 类似于拉链两侧的锯齿，指针 p 就好像拉链的拉索，将两个有序链表合并。
     * 代码中用到了一个链表算法题中很常见的虚拟头结点技巧，也就是 dummy 节点，它相当于是个占位符，可以避免处理空指针的情况，降低代码的复杂性。
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 虚拟头节点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        ListNode p1 = list1;
        ListNode p2 = list2;
        while (p1 != null && p2 != null) {
            // 比较 p1 和 p2 两个指针，将值较小的节点接到 p 指针
            if (p1.val > p2.val) {
                p.next = p2;
                p2 = p2.next;
            } else {
                p.next = p1;
                p1 = p1.next;
            }
            // p 指针不断前进
            p = p.next;
        }
        if (p1 != null) {
            p.next = p1;
        }
        if (p2 != null) {
            p.next = p2;
        }
        return dummy.next;
    }

    /**
     * 23. 合并K个升序链表
     *
     * 合并两个有序链表的延伸，利用优先级队列（二叉堆）进行节点排序即可。
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        // 虚拟头节点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // 优先级队列，最小堆
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, (t1, t2) -> t1.val - t2.val);
        // 将 K 个链表的头节点放入优先级队列中
        for (ListNode head : lists) {
            if (head != null) {
                queue.offer(head);
            }
        }
        while (!queue.isEmpty()) {
            // 获取最小节点，拼接到结果链表中
            ListNode node = queue.poll();
            p.next = node;
            if (node.next != null) {
                queue.offer(node.next);
            }
            // p 指针不断前进
            p = p.next;
        }
        return dummy.next;
    }

    /**
     * 160. 相交链表
     *
     * 用两个指针 p1 和 p2 分别在两条链表上前进，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样
     * 相当于逻辑上两条链表接在了一起。如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        // p1 指向 A 链表头节点
        ListNode p1 = headA;
        // p2 指向 B 链表头节点
        ListNode p2 = headB;
        while (p1 != p2) {
            // p1 走一步，如果走到 A 链表末尾，转到 B 链表
            if (p1 == null) {
                p1 = headB;
            } else {
                p1 = p1.next;
            }

            // p2 走一步，如果走到 B 链表末尾，转到 A 链表
            if (p2 == null) {
                p2 = headA;
            } else {
                p2 = p2.next;
            }
        }
        return p1;
    }

    /**
     * 160. 相交链表
     *
     * 另一种思路，先计算两条链表的长度，然后让 p1 和 p2 距离链表尾部的距离相同，然后齐头并进，如果相交，必定同时到达交点
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        int lenA = 0, lenB = 0;
        // 计算两条链表的长度
        for (ListNode p1 = headA; p1 != null; p1 = p1.next) {
            lenA++;
        }
        for (ListNode p2 = headB; p2 != null; p2 = p2.next) {
            lenB++;
        }
        // 让 p1 和 p2 到达尾部的距离相同
        ListNode p1 = headA, p2 = headB;
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; i++) {
                p1 = p1.next;
            }
        } else {
            for (int i = 0; i < lenB - lenA; i++) {
                p2 = p2.next;
            }
        }
        // p1 == p2 有两种情况，1：两条链表不相交，p1，p2 同时走到尾部空指针 2：两条链表相交，p1，p2 走到相交点
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }

    /**
     * 206. 反转链表(递归实现)
     *
     * @param head
     * @return
     */
    public ListNode reverse(ListNode head) {
        // 链表只有一个节点，反转也是它自己
        if (head == null || head.next == null) {
            return head;
        }
        ListNode last = reverse(head.next);
        head.next.next = head;
        // 当递归反转之后，新的头节点是 last 而之前的 head 变成了最后一个节点，别忘了链表的末尾要指向 null
        head.next = null;
        return last;
    }

    /**
     * 206. 反转链表(迭代实现)
     * 在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需
     * 要存储后一个节点。最后返回新的头节点。
     *
     * @param head
     * @return
     */
    public ListNode reverse2(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    // 后驱节点
    ListNode temp = null;

    /**
     * 反转链表的前 N 个节点
     *
     * @param head 头节点
     * @param n    n <= 链表长度
     * @return
     */
    public ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            // 记录第 n + 1 个节点
            temp = head.next;
            return head;
        }
        // 以 head.next 为起点，需要反转前 n - 1 个节点
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        // 让反转之后的 head 节点和后驱节点连起来
        head.next = temp;
        return last;
    }

    /**
     * 92. 反转链表的一部分(递归实现)
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            // 相当于反转前 n 个节点
            return reverseN(head, right);
        }
        // 前进到反转的起点，将其转化为反转前 n 个节点
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    /**
     * 92. 反转链表的一部分(迭代实现)
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween2(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        // 第一步，从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点(前驱节点)
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        // 第二步，从 pre 再走 right - left + 1 步，来到 right 节点
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        // 第三步，切断出一个子链表
        ListNode leftNode = pre.next;
        // 后驱节点
        ListNode cur = rightNode.next;

        // 第四步，切断链接
        pre.next = null;
        rightNode.next = null;

        // 第五步，反转链表的子区间
        reverse2(leftNode);

        // 第六步，接回到原来的链表中
        pre.next = rightNode;
        leftNode.next = cur;

        return dummy.next;
    }

    /**
     * 92. 反转链表的一部分(迭代实现)
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween3(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next;
        for (int i = 0; i < right - left; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummy.next;
    }
}